import jdk.internal.org.objectweb.asm.tree.IincInsnNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-11-19
 * Time: 10:43
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //这个与从上到下打印二叉树II不同的地方就是加入了方向打印，我们可以用一个布尔值控制左右方向，然后利用双端队列来控制元素的添加和弹出
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Deque<TreeNode> nodeDeque=new LinkedList<>();
        nodeDeque.offer( root );
        boolean isLeftToRight=true;
        while (!nodeDeque.isEmpty()) {
            //双向链表实现了Deque接口，具有双端队列的功能
            //这个作为一个临时的存储队列具有重要的作用，就是它来控制元素的头部输入还是尾部输入
            LinkedList<Integer> tmp=new LinkedList<>();
            int size=nodeDeque.size();
            while ( size>0 ){
                //层序遍历节点的顺序是不会变得，就是从左到右，所以弹出的节点也是按照从左到右的顺序弹出的
                //但是我们把它加入临时队列的时候可以控制顺序，即实现尾插还是头插
                TreeNode node = nodeDeque.poll();
                if(isLeftToRight){
                    //奇数层，从左到右输出元素到临时队列，那么就要把值添加到双端队列的尾部，即尾插法，正序
                    tmp.offerLast( node.val );
                }else {
                    //偶数层，从右到左输出元素到临时队列，那么就把值添加到队列的头部，即头插，实现倒序
                    tmp.offerFirst( node.val );
                }
                if(node.left!=null){
                    nodeDeque.offer(node.left);
                }
                if(node.right!=null){
                    nodeDeque.offer(node.right);
                }
                //size为0时这一层节点遍历完毕
                size--;
            }
            //size为0进入下一层的逻辑
            isLeftToRight=!isLeftToRight;
            ret.add( tmp );
        }
        return ret;
    }

}
